package leetcode_301_400;

import java.lang.annotation.Target;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class LeeCode_316_2 {
    public static void main(String[] args) {
        System.out.println(removeDuplicateLetters("cbacdcbc"));
        System.out.println(removeDuplicateLetters("bcabc"));
        System.out.println(removeDuplicateLetters("cdadabcc"));
        System.out.println(removeDuplicateLetters("ecbacba"));
        System.out.println(removeDuplicateLetters("baabc"));
        System.out.println(removeDuplicateLetters("bbcaac"));
    }
    private static String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)){
                map.put(c, map.get(c) + 1);
            }else {
                map.put(c, 1);
            }
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (stack.size() == 0){
                stack.push(c);
                map.put(c, map.get(c) - 1);
                continue;
            }
            Character peek = stack.peek();
            if (stack.contains(c)){
                map.put(c, map.get(c) - 1);
                continue;
            }
            while (peek > c && map.get(peek) > 0){
                stack.pop();
                if (stack.isEmpty())
                    break;
                peek = stack.peek();
            }
            stack.push(c);
            map.put(c, map.get(c) - 1);
        }
        StringBuilder ans = new StringBuilder();
        for (Character c : stack) {
            ans.append(c);
        }
        return ans.toString();
    }
}
